LeetCode——最长上升子序列

NO.65 最长上升子序列 中等

刚看到题，我以为寻找的这个上升子序列需要是连续的递增元素，所以我想双指针。发现行不通，重新审题发现，示例中的子序列元素不是连续的。。。

思路一：动态规划

dp数组含义：dp[i]nums前i个元素中最长上升子序列的长度。

初始化：初始状态全部为1，因为每个元素自身至少是长度为1子序列。

状态转移：填写dp[i]时遍历j∈[0,i，

如果i元素>j元素则当前元素i可以接在j元素之后作为上升子序列dp[i]=Max(dp[i],dp[j]+1)；

否则i元素<=j元素当前元素i不能拼接在j元素之后就忽略。

每次填写完dp[i]更新当前最长上升子序列长度。

public int lengthOfLIS(int[] nums) {
    if (nums==null||nums.length==0)return 0;
    int[] dp=new int[nums.length];
    int maxLen=0;
    //初始化
    Arrays.fill(dp,1);
    //状态转移
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            //如果i元素>j元素，则i可以接在j元素后面作为上升子序列
            if (nums[i]>nums[j])dp[i]=Math.max(dp[i],dp[j]+1);
        }
        //更新最大长度
        maxLen=Math.max(maxLen,dp[i]);
    }
    return maxLen;
}

时间复杂度：O(n^2)

思路二：TreeSet

JAVA Api中的TreeSet有ceiling(x)方法，取大于x的数，如果不存在则返回null。(此方法时间复杂度O(logn)，但是最坏情况下会退化到O(n))

按序遍历nums，到TreeSet中取大于num的数x，如果存在x则删除x并将num加入set，如果不存在就是所有的数都小于num就将num加入set。

最后返回set的大小即可。

public int lengthOfLIS(int[] nums) {
    if (nums==null||nums.length==0)return 0;
    TreeSet<Integer> set=new TreeSet<>();
    for (int num : nums) {
        Integer x = set.ceiling(num);
        if (x != null) {
            set.remove(x);
        }
        set.add(num);
    }
    return set.size();
}

最坏时间复杂度仍然是：O(n^2)

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github